home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / smaltalk / manchest.lha / MANCHESTER / manchester / 2.2 / Philosophers.st < prev    next >
Text File  |  1993-07-24  |  7KB  |  234 lines
  1. "    NAME        Philosophers
  2.     AUTHOR        tph@cs.man.ac.uk
  3.     FUNCTION Tim Budd's version of Diners problem 
  4.     ST-VERSIONS    2.2
  5.     PREREQUISITES     
  6.     CONFLICTS    
  7.     DISTRIBUTION      world
  8.     VERSION        1.1
  9.     DATE    22 Jan 1989
  10. SUMMARY    Philosophers
  11.     contains a version of the Dining Philosophers
  12.    problem, based on the implementation in Tim Budd's book ""A Little
  13.    Smalltalk"".(2.2).TPH
  14. "!
  15. Object subclass: #DiningPhilosophers
  16.     instanceVariableNames: 'numberDiners chopSticks philosophers '
  17.     classVariableNames: ''
  18.     poolDictionaries: ''
  19.     category: 'Dining Philosophers'!
  20. DiningPhilosophers comment:
  21. 'This is a Smalltalk representation of Dijkstra''s Dining Philosophers Problem.  The solution presented here is loosely based on the one written in Little Smalltalk, presented in Tim Budd''s book "A Little Smalltalk", pp. 116-121.
  22.  
  23. "Five philosophers spend their lives eating and thinking.  The philosophers share a common circular table surrounded by five chairs, each belonging to one philosopher.  In the centre of the table, there is a bowl of rice and the table is laid with five chopsticks.  When a philosopher thinks, he does not interact with his colleagues.  From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to him (the chopsticks that are between him and his left and right neighbours).  A philosopher may only pick up one chopstick at a time.  Obviously, he cannot pick up a chopstick that is already in the hand of a neighbour.  When a hungry philosopher has both his chopsticks at the same time, he eats without releasing his chopsticks.  When he has finished eating, he puts down both of his chopsticks and starts thinking again."
  24.  
  25. The solution represents each chopstick as a Semaphore, using the ''wait'' and ''signal'' methods.  This guarantees that no two philosophers use the same chopstick simultaneously.  The solution is also asymmetric; an odd philosopher picks up his left chopstick first, then his right chopstick, while an even philosopher picks up his right chopstick first.
  26.  
  27. Each philosopher is represented by an instance of class Philosopher; the philosophers and the chopsticks are maintained in instance variables.
  28.  
  29. '!
  30.  
  31.  
  32. !DiningPhilosophers methodsFor: 'accessing'!
  33.  
  34. chopSticks
  35.     "Answer with the array containing the chopsticks."
  36.  
  37.     ^chopSticks!
  38.  
  39. chopSticks: anArray
  40.     "Set up the chopsticks at the table."
  41.  
  42.     chopSticks _ anArray!
  43.  
  44. numberDiners
  45.     "Answer with the number of diners at the table."
  46.  
  47.     ^numberDiners!
  48.  
  49. numberDiners: aNumber
  50.     "Set the number of diners at the table."
  51.  
  52.     numberDiners _ aNumber!
  53.  
  54. philosophers
  55.     "Answer with the array containing the philosophers."
  56.  
  57.     ^philosophers!
  58.  
  59. philosophers: anArray
  60.     "Sets up the array containing the philosophers."
  61.  
  62.     philosophers _ anArray! !
  63.  
  64. !DiningPhilosophers methodsFor: 'dining'!
  65.  
  66. dine: time
  67.     "The table representing the dining philosophers eating a
  68.      meal 'time' times a day. "
  69.  
  70.     1 to: self numberDiners do: [:p |
  71.         (self philosophers at: p) philosophize: time].! !
  72.  
  73. !DiningPhilosophers methodsFor: 'initialize-release'!
  74.  
  75. initialize: aNumber
  76.     "Initialize an instance of the Dining Philosophers problem, for
  77.      aNumber diners."
  78.  
  79.     self numberDiners: aNumber.
  80.     self chopSticks: (Array new: aNumber).
  81.     self philosophers: (Array new: aNumber).
  82.  
  83.     1 to: aNumber do: [:p |
  84.         self chopSticks at: p put: (Semaphore new signal).
  85.         self philosophers at: p put: (Philosopher new: p)].
  86.  
  87.     1 to: aNumber do: [:p |
  88.         (self philosophers at: p)
  89.             leftChopStick: (self chopSticks at: p)
  90.             rightChopStick: (self chopSticks at: ((p \\ aNumber) + 1))].! !
  91. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  92.  
  93. DiningPhilosophers class
  94.     instanceVariableNames: ''!
  95.  
  96.  
  97. !DiningPhilosophers class methodsFor: 'examples'!
  98.  
  99. example1
  100.     "Create a dining table for 5 philosophers."
  101.     "DiningPhilosophers example1."
  102.  
  103.     | table |
  104.     table _ DiningPhilosophers new: 5.
  105.     table dine: 2! !
  106.  
  107. !DiningPhilosophers class methodsFor: 'instance creation'!
  108.  
  109. new: aNumber
  110.     "Create a new instance of the Dining Philosophers problem, for
  111.      aNumber diners."
  112.  
  113.     ^super new initialize: aNumber! !
  114.  
  115. Object subclass: #Philosopher
  116.     instanceVariableNames: 'leftChopStick rightChopStick name '
  117.     classVariableNames: ''
  118.     poolDictionaries: ''
  119.     category: 'Dining Philosophers'!
  120. Philosopher comment:
  121. 'I represent a philosopher who may be eating and thinking at a table.  I have a unique ''name'', and I know which is my left and right chopsticks.
  122.  
  123. '!
  124.  
  125.  
  126. !Philosopher methodsFor: 'printing'!
  127.  
  128. printState: state
  129.     "Show the state of the receiver."
  130.  
  131.     Transcript cr; show: 'Philosopher ', self name printString,' is ',state! !
  132.  
  133. !Philosopher methodsFor: 'random numbers'!
  134.  
  135. randInteger: aNumber 
  136.     "Answer with a random integer between 0 and aNumber inclusive."
  137.  
  138.     | rand |
  139.     rand _ Random new.
  140.     ^(rand next * aNumber) rounded! !
  141.  
  142. !Philosopher methodsFor: 'synchronization'!
  143.  
  144. eat
  145.     "Eat for a while.  Release the processor a random number of times
  146.      to include some non-determinism in the solution."
  147.  
  148.     self printState: 'eating'.
  149.     (self randInteger: 15) timesRepeat: [Processor yield]!
  150.  
  151. getChopSticks
  152.     "Attempt to get the adjacent chopsticks."
  153.  
  154.     self printState: 'getting hungry'.
  155.     (name \\ 2) == 0
  156.         ifTrue: [self leftChopStick wait.  self rightChopStick wait]
  157.         ifFalse: [self rightChopStick wait.  self leftChopStick wait]!
  158.  
  159. philosophize: time
  160.     "One day in the life of a Philosopher. He eats
  161.      'time' times per day, then goes to sleep."
  162.  
  163.     [time timesRepeat: [
  164.         self think.
  165.         self getChopSticks.
  166.         self eat.
  167.         self releaseChopSticks].
  168.     self printState: 'sleeping'.
  169.     ] fork!
  170.  
  171. releaseChopSticks
  172.     "Let go of both chopsticks."
  173.  
  174.     self printState: 'finished'.
  175.     self leftChopStick signal.
  176.     self rightChopStick signal!
  177.  
  178. think
  179.     "Think for a while.  Release the processor a random number of times
  180.      to include some non-determinism in the solution."
  181.  
  182.     self printState: 'thinking'.
  183.     (self randInteger: 15) timesRepeat: [Processor yield]! !
  184.  
  185. !Philosopher methodsFor: 'accessing'!
  186.  
  187. leftChopStick
  188.     "Answer with the left chopstick"
  189.  
  190.     ^leftChopStick!
  191.  
  192. leftChopStick: aChopStick
  193.     "Set the left chopstick"
  194.  
  195.     leftChopStick _ aChopStick!
  196.  
  197. leftChopStick: lChop rightChopStick: rChop
  198.     "Set both chopsticks."
  199.  
  200.     self leftChopStick: lChop.
  201.     self rightChopStick: rChop!
  202.  
  203. name
  204.     "Answer with the Philosopher's name."
  205.  
  206.     ^name!
  207.  
  208. name: aNumber
  209.     "Set the Philosopher's name."
  210.  
  211.     name _ aNumber!
  212.  
  213. rightChopStick
  214.     "Answer with the right chopstick"
  215.  
  216.     ^rightChopStick!
  217.  
  218. rightChopStick: aChopStick
  219.     "Set the right chopstick"
  220.  
  221.     rightChopStick _ aChopStick! !
  222. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  223.  
  224. Philosopher class
  225.     instanceVariableNames: ''!
  226.  
  227.  
  228. !Philosopher class methodsFor: 'instance creation'!
  229.  
  230. new: aNumber
  231.     "Create a new Philosopher with name aNumber."
  232.  
  233.     ^super new name: aNumber! !    ^super new name: aNumber! !
  234.